package Q2;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public static int maxLength (int[] arr) {
        // write code here

        int n = arr.length;
        int[] dp = new int[n + 1];
        Map<Integer, Integer> map = new HashMap<>(); //key 为子数组中已经存在哪些元素，value 为该元素在 dp 中的下标
        Queue<Integer> queue = new LinkedList<>();


        for (int i = 1; i < n + 1; i++) {
            if (map.containsKey(arr[i - 1])) {
                //找到这个已经有的元素的下标
                dp[i] = dp[i - 1] - 1;
                int dpIndex = map.get(arr[i - 1]);
                int count = dpIndex;
                while (count > 0) {
                    count--;
                    queue.poll();
                }
            } else {
                queue.offer(arr[i - 1]);
                dp[i] = dp[i - 1] + 1;
            }
            map.put(arr[i - 1], i);
        }

        int ret = 0;
        for (int i = 0; i < n + 1; i++) {
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }

    public static void main(String[] args) {
        System.out.println(maxLength(new int[]{1,2,3,4,2,5,6}));
    }
}
